package _02_greedy_algorithm;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringJoiner;

/**
 * @author: mornd
 * @dateTime: 2023/7/20 - 15:46
 * 分数背包问题
 */
public class FractionalKnapsackProblem {

    static class Item {
        int index;
        int weight;
        int value;

        // 计算单价
        public int unitValue() {
            return value / weight;
        }

        public Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }

        @Override
        public String toString() {
            return new StringJoiner(", ", Item.class.getSimpleName() + "[", "]")
                    .add("index=" + index)
                    .add("weight=" + weight)
                    .add("value=" + value)
                    .toString();
        }
    }

    public static void main(String[] args) {
        /*
            背包中有如下物品，若指定要拿出n升，怎样拿能保证n升是最贵的（可以每样拿一部分）？
            编号   重量(升)  价值
            0     4        24      水
            1     8        160     牛奶
            2     2        4000    五粮液
            3     6        108     可乐
            4     1        4000    茅台

         */
        Item[] items = new Item[]{
                new Item(0, 4, 24),
                new Item(1, 8, 160),    // 7
                new Item(2, 2, 4000),   // 2
                new Item(3, 6, 108),
                new Item(4, 1, 4000)  // 1
        };

        int price = select(items, 10);
        System.out.println("price = " + price);
    }

    private static int select(Item[] items, int total) {
        // 按单价降序
        PriorityQueue<Item> queue = new PriorityQueue<>(
                Comparator.comparingInt(Item::unitValue).reversed()
        );
        queue.addAll(Arrays.stream(items).toList());
        int price = 0;

        while (total > 0) {
            Item poll = queue.poll();
            if (poll.weight > total) {
                price += total * poll.unitValue();
                break;
            } else {
                total -= poll.weight;
                price += poll.value;
            }
        }

        return price;
    }
}
